A quantizer is a device for converting numerical data into a finite number of possible outputs. That is, the input to a quantizer may be any value, but the output of a quantizer is limited to only certain values. The function of a quantizer is to determine which of its possible output values is closest to the input value and put out that value. For example, a flip-flop puts out either a voltage equal to the power supply voltage connected to the flip-flop (e.g., five volts or a logic one) or a voltage equal to the ground voltage connected to the flip-flop (e.g., zero volts or a logic zero). The input to a flip-flop may be any value between ground voltage and the power supply voltage. The flip-flop determines which of its two possible output values is closest to the input value and puts out that value. Typically, an input voltage greater than or equal to one-half of the power supply voltage will cause a flip-flop to put out the power supply voltage (i.e., a logic one) while an input voltage below one-half of the power supply voltage will cause a flip-flop to put out the ground voltage (i.e., a logic zero).
Quantizers are used in the design of signals for use over a noisy channel. Analog to Digital converters convert complex analog signals (e.g., 0.654783V) into simplistic digital signals (e.g., logic 1). This is a form of data compression. An area centered at one of the allowable outputs is called a Voronoi region. If the quantizer receives a point in this region, it converts it, if necessary, to the allowable point in the center of the region.
Quantizers come in two types (i.e., scaler quantizers and vector quantizers). A scalar quantizer quantizes data from a single source by rounding a real number to its nearest output value (e.g., a flip-flop). A vector quantizer quantizes data from multiple sources by choosing one point from a finite set of points in n-dimensional space that is closest to the point represented by the input vector. A point in n-dimensional space is simply a string of n real numbers. That is, x=(x.sub.1, x.sub.2, x.sub.3, . . . ,x.sub.n). For example, a point in three dimensional space is a point represented by three coordinates, a point in four dimensional space is a point represented by four coordinates, and so on. The allowed output values of a vector quantizer are called centroids.
The present invention concerns a lattice quantizer. A lattice in n-dimensional space is defined as follows. Let (v.sub.1, v.sub.2, . . . ,v.sub.n) be a set of n linearly independent vectors in n-dimensional space. The lattice generated by (v.sub.1, v.sub.2, . . . ,v.sub.n) is the set (c.sub.1 v.sub.1 +c.sub.2 v.sub.2 + . . . . +c.sub.n v.sub.n), where c.sub.i is an integer. The vectors v.sub.1,v.sub.2, . . . ,v.sub.n form a basis for the lattice. If x=(x.sub.1,x.sub.2, . . . ,x.sub.n) then the norm of x is equal to (x.sub.1 2+x.sub.2 2+ . . . +x.sub.n 2), where " " denotes exponentiation. A sphere in n-dimensional space with center u=(u.sub.1,u.sub.2, . . . ,u.sub.n) and radius p consists of all the points x=(x.sub.1,x.sub.2, . . . ,x.sub.n) satisfying (x.sub.1 -u.sub.1) 2+(x.sub.2 -u.sub.2) 2+ . . . +(x.sub.n -u.sub.n) 2=p 2. A sphere packing, or shell packing, is described by specifying the centers u and the radius p. When the centers of a group of spheres form a lattice, the packing is referred to as a lattice packing. A lattice packing always has a center at a point designated as an origin with the remaining centers on concentric spheres around the origin. The shells are numbered according to their proximity to the center or origin point. That is, the shell closest to the origin point is shell 1, the shell second closest to the origin point is shell 2, and so on. If one lattice may be obtained from another by rotation, reflection, or change of scale then it is said that the lattices are equivalent or similar.
Mathematicians continue to look for dense packings of n-dimensional spheres because there are important practical applications of sphere packing to problems arising in digital communications. A finite subset of the points on the surface of a sphere is called a spherical code. Spherical codes may be constructed from sphere packings. The sphere packing density of a lattice is defined by the number of spheres that fit within a particular volume. A kissing number of a lattice is defined as the number of spheres that a sphere in the lattice touches. The eight-dimensional lattice, designated as E8, has the highest sphere packing density and the highest possible kissing number in eight dimensions.
In a lattice quantizer, the centroids are grid points in n-dimensional space. The advantage of using a lattice quantizer is that the centroids are already known and do not have to be calculated from the input data. The disadvantage of using a lattice quantizer is that there are an infinite number of centroids. Because of this, lattice quantizers are only appropriate for quantizing data that has a probability distribution that is heavily concentrated around a single point in n-dimensional space (e.g., the origin).
Quantizing introduces error. The magnitude of the error is the distance from the received point to the acceptable point. The acceptable points are chosen to minimize the error, or more precisely, to minimize the mean squared error. For various dimensions, the mean squared error has been determined. It may be shown that higher dimension quantizers have lower errors per symbol than do lower dimension quantizers. Higher dimension quantizers with their lower errors provide better quantization than do lower dimension quantizers. However, higher dimension quantizers require more capability than lower dimension quantizers and are, therefore, more expensive than lower dimension quantizers. Therefore, a quantizer designer may choose the minimum dimension quantizer that has an acceptable error. It can be shown that going from one dimension to eight dimensions (an addition of seven symbols) reduces the mean squared error from 0.083333 to 0.071682 for an improvement of 2% per added symbol. Above eight dimensions, there is a diminished return for each added symbol. For example, at twelve dimensions the improvement in mean squared error is only 1.45% per added symbol above one dimension. For sixteen dimensions, there is only a 1.2% improvement in the mean squared error per symbol above one dimension. For twenty-four dimensions, there is only a 0.91% improvement in mean squared error per symbol above one dimensions. So, eight dimension quantizers appear to be the most economical quantizers to build.
Quantizers may be used to design signals for data transmission or storage systems (e.g., error correcting codes). A code is a set of signals to be transmitted. Only these codes will be transmitted over a channel. The members of a code are designed to be easily distinguished from the other members of the code even in the presence of noise. Noise may corrupt a particular member of the code, but it is intended that the corrupted code will be identified as the particular code that was transmitted. So, a message to be sent is encoded, sent over a noisy channel, and decoded to recover the message.
Certain important lattices include the cubic lattice Z n, the root lattices (i.e., An, Dn, E6, E7, and E8), the Coxeter-Todd lattice K12, the sixteen dimensional Barnes-Wall lattice, the 24 dimensional Leech lattice, and their duals. These lattices include the best quantizers.
U.S. Pat. No. 5,150,209, entitled "HIERARCHICAL ENTROPY CODED LATTICE THRESHOLD QUANTIZATION ENCODING METHOD AND APPARATUS FOR IMAGE AND VIDEO COMPRESSION," discloses an eight dimensional lattice quantizer based on the E8 lattice that requires the storage of 920 points to encode and decode 2400 points that do not round to the origin point but instead round to a codeword in either shell 1 or shell 2. A reduction in storage from 2400 to 920 (i.e., a 60% improvement) is achieved using the quantizer of U.S. Pat. No. 5,150,209. The present invention uses a rotated equivalent lattice to improve upon the quantizer of U.S. Pat. No. 5,150,209 by reducing even further the number of points that are stored to encode and decode 2400 points that do not round to the origin point. The present invention reduces the number of codewords that must be stored to 16. This is a 98% improvement over the method of U.S. Pat. No. 5,150,209. U.S. Pat. No. 5,150,209 is hereby incorporated by reference into the specification of the present invention.
In three articles authored by John H. Conway and N. J. A. Sloane, entitled "Fast 4- and 8-Dimensional Quantizers and Decoders," IEEE, 1981, pps. F4.2.1-F4.2.4, "Fast Quantizing and Decoding Algorithms for Lattice Quantizers and Codes," IEEE Transactions on Information Theory, Vol. IT-28, No. 2, March 1982, and "Soft Decoding Techniques for Codes and Lattices, Including the Golay Code and the Leech Lattice," IEEE Transactions on Information Theory, Vol. IT-32, No. 1, January 1986, mathematical techniques associated with lattice quantizers are disclosed but the present invention which minimizes the storage requirement and the computational complexity of an eight dimensional lattice quantizer is not disclosed therein.